home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / Python 1.3.3 / Python 133 SRC / Modules / parsermodule.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-01-22  |  55.3 KB  |  2,177 lines  |  [TEXT/CWIE]
  1. /*  Parser.c
  2.  *
  3.  *  Copyright 1995 by Fred L. Drake, Jr. and Virginia Polytechnic Institute
  4.  *  and State University, Blacksburg, Virginia, USA.  Portions copyright
  5.  *  1991-1995 by Stichting Mathematisch Centrum, Amsterdam, The Netherlands.
  6.  *  Copying is permitted under the terms associated with the main Python
  7.  *  distribution, with the additional restriction that this additional notice
  8.  *  be included and maintained on all distributed copies.
  9.  *
  10.  *  This module serves to replace the original parser module written by
  11.  *  Guido.  The functionality is not matched precisely, but the original
  12.  *  may be implemented on top of this.  This is desirable since the source
  13.  *  of the text to be parsed is now divorced from this interface.
  14.  *
  15.  *  Unlike the prior interface, the ability to give a parse tree produced
  16.  *  by Python code as a tuple to the compiler is enabled by this module.
  17.  *  See the documentation for more details.
  18.  *
  19.  */
  20.  
  21. #include "Python.h"            /* general Python API          */
  22. #include "graminit.h"            /* symbols defined in the grammar */
  23. #include "node.h"            /* internal parser structure      */
  24. #include "token.h"            /* token definitions          */
  25.                     /* ISTERMINAL() / ISNONTERMINAL() */
  26.  
  27. /*
  28.  *  All the "fudge" declarations are here:
  29.  */
  30.  
  31.  
  32. /*  These appearantly aren't prototyped in any of the standard Python headers,
  33.  *  either by this name or as 'parse_string()/compile().'  This works at
  34.  *  cutting out the warning, but needs to be done as part of the mainstream
  35.  *  Python headers if this is going to be supported.  It is being handled as
  36.  *  part of the Great Renaming.
  37.  */
  38. extern node*     PyParser_SimpleParseString(char*, int);
  39. extern PyObject* PyNode_Compile(node*, char*);
  40.  
  41.  
  42. /*  This isn't part of the Python runtime, but it's in the library somewhere.
  43.  *  Where it is varies a bit, so just declare it.
  44.  */
  45. extern char* strdup(const char*);
  46.  
  47.  
  48. /*
  49.  *  That's it!  Now, on to the module....
  50.  */
  51.  
  52.  
  53.  
  54. /*  String constants used to initialize module attributes.
  55.  *
  56.  */
  57. static char*
  58. parser_copyright_string
  59. = "Copyright 1995 by Virginia Polytechnic Institute & State University and\n"
  60.   "Fred L. Drake, Jr., Blacksburg, Virginia, USA.  Portions copyright\n"
  61.   "1991-1995 by Stichting Mathematisch Centrum, Amsterdam, The Netherlands.";
  62.  
  63.  
  64. static char*
  65. parser_doc_string
  66. = "This is an interface to Python's internal parser.";
  67.  
  68. static char*
  69. parser_version_string = "0.1";
  70.  
  71.  
  72. /*  The function below is copyrigthed by Stichting Mathematisch Centrum.
  73.  *  original copyright statement is included below, and continues to apply
  74.  *  in full to the function immediately following.  All other material is
  75.  *  original, copyrighted by Fred L. Drake, Jr. and Virginia Polytechnic
  76.  *  Institute and State University.  Changes were made to comply with the
  77.  *  new naming conventions.
  78.  */
  79.  
  80. /***********************************************************
  81. Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
  82. The Netherlands.
  83.  
  84.                         All Rights Reserved
  85.  
  86. Permission to use, copy, modify, and distribute this software and its 
  87. documentation for any purpose and without fee is hereby granted, 
  88. provided that the above copyright notice appear in all copies and that
  89. both that copyright notice and this permission notice appear in 
  90. supporting documentation, and that the names of Stichting Mathematisch
  91. Centrum or CWI not be used in advertising or publicity pertaining to
  92. distribution of the software without specific, written prior permission.
  93.  
  94. STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
  95. THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  96. FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
  97. FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  98. WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  99. ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  100. OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  101.  
  102. ******************************************************************/
  103.  
  104. static PyObject*
  105. node2tuple(n)
  106.     node *n;
  107. {
  108.     if (n == NULL) {
  109.         Py_INCREF(Py_None);
  110.         return Py_None;
  111.     }
  112.     if (ISNONTERMINAL(TYPE(n))) {
  113.         int i;
  114.         PyObject *v, *w;
  115.         v = PyTuple_New(1 + NCH(n));
  116.         if (v == NULL)
  117.             return v;
  118.         w = PyInt_FromLong(TYPE(n));
  119.         if (w == NULL) {
  120.             Py_DECREF(v);
  121.             return NULL;
  122.         }
  123.         PyTuple_SetItem(v, 0, w);
  124.         for (i = 0; i < NCH(n); i++) {
  125.             w = node2tuple(CHILD(n, i));
  126.             if (w == NULL) {
  127.                 Py_DECREF(v);
  128.                 return NULL;
  129.             }
  130.             PyTuple_SetItem(v, i+1, w);
  131.         }
  132.         return v;
  133.     }
  134.     else if (ISTERMINAL(TYPE(n))) {
  135.         return Py_BuildValue("(is)", TYPE(n), STR(n));
  136.     }
  137.     else {
  138.         PyErr_SetString(PyExc_SystemError,
  139.                "unrecognized parse tree node type");
  140.         return NULL;
  141.     }
  142. }
  143. /*
  144.  *  End of material copyrighted by Stichting Mathematisch Centrum.
  145.  */
  146.  
  147.  
  148.  
  149. /*  There are two types of intermediate objects we're interested in:
  150.  *  'eval' and 'exec' types.  These constants can be used in the ast_type
  151.  *  field of the object type to identify which any given object represents.
  152.  *  These should probably go in an external header to allow other extensions
  153.  *  to use them, but then, we really should be using C++ too.  ;-)
  154.  *
  155.  *  The PyAST_FRAGMENT type is not currently supported.
  156.  */
  157.  
  158. #define PyAST_EXPR    1
  159. #define PyAST_SUITE    2
  160. #define PyAST_FRAGMENT    3
  161.  
  162.  
  163. /*  These are the internal objects and definitions required to implement the
  164.  *  AST type.  Most of the internal names are more reminiscent of the 'old'
  165.  *  naming style, but the code uses the new naming convention.
  166.  */
  167.  
  168. static PyObject*
  169. parser_error = 0;
  170.  
  171.  
  172. typedef struct _PyAST_Object {
  173.  
  174.     PyObject_HEAD            /* standard object header        */
  175.     node* ast_node;            /* the node* returned by the parser */
  176.     int      ast_type;            /* EXPR or SUITE ?            */
  177.  
  178. } PyAST_Object;
  179.  
  180.  
  181. staticforward void parser_free(PyAST_Object* ast);
  182. staticforward int  parser_compare(PyAST_Object* left, PyAST_Object* right);
  183. staticforward long parser_hash(PyAST_Object* ast);
  184.  
  185.  
  186. /* static */
  187. PyTypeObject PyAST_Type = {
  188.  
  189.     PyObject_HEAD_INIT(&PyType_Type)
  190.     0,
  191.     "ast",                /* tp_name        */
  192.     sizeof(PyAST_Object),        /* tp_basicsize        */
  193.     0,                    /* tp_itemsize        */
  194.     (destructor)parser_free,        /* tp_dealloc        */
  195.     0,                    /* tp_print        */
  196.     0,                    /* tp_getattr        */
  197.     0,                    /* tp_setattr        */
  198.     (cmpfunc)parser_compare,        /* tp_compare        */
  199.     0,                    /* tp_repr        */
  200.     0,                    /* tp_as_number        */
  201.     0,                    /* tp_as_sequence    */
  202.     0,                    /* tp_as_mapping    */
  203.     0,                    /* tp_hash        */
  204.     0,                    /* tp_call        */
  205.     0                    /* tp_str        */
  206.  
  207. };  /* PyAST_Type */
  208.  
  209.  
  210. static int
  211. parser_compare_nodes(left, right)
  212.      node* left;
  213.      node* right;
  214. {
  215.     int j;
  216.  
  217.     if (TYPE(left) < TYPE(right))
  218.     return (-1);
  219.  
  220.     if (TYPE(right) < TYPE(left))
  221.     return (1);
  222.  
  223.     if (ISTERMINAL(TYPE(left)))
  224.     return (strcmp(STR(left), STR(right)));
  225.  
  226.     if (NCH(left) < NCH(right))
  227.     return (-1);
  228.  
  229.     if (NCH(right) < NCH(left))
  230.     return (1);
  231.  
  232.     for (j = 0; j < NCH(left); ++j) {
  233.     int v = parser_compare_nodes(CHILD(left, j), CHILD(right, j));
  234.  
  235.     if (v)
  236.         return (v);
  237.     }
  238.     return (0);
  239.  
  240. }   /* parser_compare_nodes() */
  241.  
  242.  
  243. /*  int parser_compare(PyAST_Object* left, PyAST_Object* right)
  244.  *
  245.  *  Comparison function used by the Python operators ==, !=, <, >, <=, >=
  246.  *  This really just wraps a call to parser_compare_nodes() with some easy
  247.  *  checks and protection code.
  248.  *
  249.  */
  250. static int
  251. parser_compare(left, right)
  252.      PyAST_Object* left;
  253.      PyAST_Object* right;
  254. {
  255.     if (left == right)
  256.     return (0);
  257.  
  258.     if ((left == 0) || (right == 0))
  259.     return (-1);
  260.  
  261.     return (parser_compare_nodes(left->ast_node, right->ast_node));
  262.  
  263. }   /* parser_compare() */
  264.  
  265.  
  266. /*  parser_newastobject(node* ast)
  267.  *
  268.  *  Allocates a new Python object representing an AST.  This is simply the
  269.  *  'wrapper' object that holds a node* and allows it to be passed around in
  270.  *  Python code.
  271.  *
  272.  */
  273. static PyObject*
  274. parser_newastobject(ast, type)
  275.      node* ast;
  276.      int   type;
  277. {
  278.     PyAST_Object* o = PyObject_NEW(PyAST_Object, &PyAST_Type);
  279.  
  280.     if (o != 0) {
  281.     o->ast_node = ast;
  282.     o->ast_type = type;
  283.     }
  284.     return ((PyObject*)o);
  285.  
  286. }   /* parser_newastobject() */
  287.  
  288.  
  289. /*  void parser_free(PyAST_Object* ast)
  290.  *
  291.  *  This is called by a del statement that reduces the reference count to 0.
  292.  *
  293.  */
  294. static void
  295. parser_free(ast)
  296.      PyAST_Object* ast;
  297. {
  298.     PyNode_Free(ast->ast_node);
  299.     PyMem_DEL(ast);
  300.  
  301. }   /* parser_free() */
  302.  
  303.  
  304. /*  parser_ast2tuple(PyObject* self, PyObject* args)
  305.  *
  306.  *  This provides conversion from a node* to a tuple object that can be
  307.  *  returned to the Python-level caller.  The AST object is not modified.
  308.  *
  309.  */
  310. static PyObject*
  311. parser_ast2tuple(self, args)
  312.      PyObject* self;
  313.      PyObject* args;
  314. {
  315.     PyObject* ast;
  316.     PyObject* res = 0;
  317.  
  318.     if (PyArg_ParseTuple(args, "O!:ast2tuple", &PyAST_Type, &ast)) {
  319.     /*
  320.      *  Convert AST into a tuple representation.  Use Guido's function,
  321.      *  since it's known to work already.
  322.      */
  323.     res = node2tuple(((PyAST_Object*)ast)->ast_node);
  324.     }
  325.     return (res);
  326.  
  327. }   /* parser_ast2tuple() */
  328.  
  329.  
  330. /*  parser_compileast(PyObject* self, PyObject* args)
  331.  *
  332.  *  This function creates code objects from the parse tree represented by
  333.  *  the passed-in data object.  An optional file name is passed in as well.
  334.  *
  335.  */
  336. static PyObject*
  337. parser_compileast(self, args)
  338.      PyObject* self;
  339.      PyObject* args;
  340. {
  341.     PyAST_Object* ast;
  342.     PyObject*     res = 0;
  343.     char*      str = "<ast>";
  344.  
  345.     if (PyArg_ParseTuple(args, "O!|s", &PyAST_Type, &ast, &str))
  346.     res = PyNode_Compile(ast->ast_node, str);
  347.  
  348.     return (res);
  349.  
  350. }   /* parser_compileast() */
  351.  
  352.  
  353. /*  PyObject* parser_isexpr(PyObject* self, PyObject* args)
  354.  *  PyObject* parser_issuite(PyObject* self, PyObject* args)
  355.  *
  356.  *  Checks the passed-in AST object to determine if it is an expression or
  357.  *  a statement suite, respectively.  The return is a Python truth value.
  358.  *
  359.  */
  360. static PyObject*
  361. parser_isexpr(self, args)
  362.      PyObject* self;
  363.      PyObject* args;
  364. {
  365.     PyAST_Object* ast;
  366.     PyObject* res = 0;
  367.  
  368.     if (PyArg_ParseTuple(args, "O!:isexpr", &PyAST_Type, &ast)) {
  369.     /*
  370.      *  Check to see if the AST represents an expression or not.
  371.      */
  372.     res = (ast->ast_type == PyAST_EXPR) ? Py_True : Py_False;
  373.     Py_INCREF(res);
  374.     }
  375.     return (res);
  376.  
  377. }   /* parser_isexpr() */
  378.  
  379.  
  380. static PyObject*
  381. parser_issuite(self, args)
  382.      PyObject* self;
  383.      PyObject* args;
  384. {
  385.     PyAST_Object* ast;
  386.     PyObject* res = 0;
  387.  
  388.     if (PyArg_ParseTuple(args, "O!:isexpr", &PyAST_Type, &ast)) {
  389.     /*
  390.      *  Check to see if the AST represents an expression or not.
  391.      */
  392.     res = (ast->ast_type == PyAST_EXPR) ? Py_False : Py_True;
  393.     Py_INCREF(res);
  394.     }
  395.     return (res);
  396.  
  397. }   /* parser_issuite() */
  398.  
  399.  
  400. /*  PyObject* parser_do_parse(PyObject* args, int type)
  401.  *
  402.  *  Internal function to actually execute the parse and return the result if
  403.  *  successful, or set an exception if not.
  404.  *
  405.  */
  406. static PyObject*
  407. parser_do_parse(args, type)
  408.      PyObject *args;
  409.      int      type;
  410. {
  411.     char*     string = 0;
  412.     PyObject* res    = 0;
  413.  
  414.     if (PyArg_ParseTuple(args, "s", &string)) {
  415.     node* n = PyParser_SimpleParseString(string,
  416.                          (type == PyAST_EXPR)
  417.                          ? eval_input : file_input);
  418.  
  419.     if (n != 0)
  420.         res = parser_newastobject(n, type);
  421.     else
  422.         PyErr_SetString(parser_error, "Could not parse string.");
  423.     }
  424.     return (res);
  425.  
  426. }  /* parser_do_parse() */
  427.  
  428.  
  429. /*  PyObject* parser_expr(PyObject* self, PyObject* args)
  430.  *  PyObject* parser_suite(PyObject* self, PyObject* args)
  431.  *
  432.  *  External interfaces to the parser itself.  Which is called determines if
  433.  *  the parser attempts to recognize an expression ('eval' form) or statement
  434.  *  suite ('exec' form).  The real work is done by parser_do_parse() above.
  435.  *
  436.  */
  437. static PyObject*
  438. parser_expr(self, args)
  439.      PyObject* self;
  440.      PyObject* args;
  441. {
  442.     return (parser_do_parse(args, PyAST_EXPR));
  443.  
  444. }   /* parser_expr() */
  445.  
  446.  
  447. static PyObject*
  448. parser_suite(self, args)
  449.      PyObject* self;
  450.      PyObject* args;
  451. {
  452.     return (parser_do_parse(args, PyAST_SUITE));
  453.  
  454. }   /* parser_suite() */
  455.  
  456.  
  457.  
  458. /*  This is the messy part of the code.  Conversion from a tuple to an AST
  459.  *  object requires that the input tuple be valid without having to rely on
  460.  *  catching an exception from the compiler.  This is done to allow the
  461.  *  compiler itself to remain fast, since most of its input will come from
  462.  *  the parser directly, and therefore be known to be syntactically correct.
  463.  *  This validation is done to ensure that we don't core dump the compile
  464.  *  phase, returning an exception instead.
  465.  *
  466.  *  Two aspects can be broken out in this code:  creating a node tree from
  467.  *  the tuple passed in, and verifying that it is indeed valid.  It may be
  468.  *  advantageous to expand the number of AST types to include funcdefs and
  469.  *  lambdadefs to take advantage of the optimizer, recognizing those ASTs
  470.  *  here.  They are not necessary, and not quite as useful in a raw form.
  471.  *  For now, let's get expressions and suites working reliably.
  472.  */
  473.  
  474.  
  475. staticforward node* build_node_tree(PyObject*);
  476. staticforward int   validate_expr_tree(node*);
  477. staticforward int   validate_suite_tree(node*);
  478.  
  479.  
  480. /*  PyObject* parser_tuple2ast(PyObject* self, PyObject* args)
  481.  *
  482.  *  This is the public function, called from the Python code.  It receives a
  483.  *  single tuple object from the caller, and creates an AST object if the
  484.  *  tuple can be validated.  It does this by checking the first code of the
  485.  *  tuple, and, if acceptable, builds the internal representation.  If this
  486.  *  step succeeds, the internal representation is validated as fully as
  487.  *  possible with the various validate_*() routines defined below.
  488.  *
  489.  *  This function must be changed if support is to be added for PyAST_FRAGMENT
  490.  *  AST objects.
  491.  *
  492.  */
  493. static PyObject*
  494. parser_tuple2ast(self, args)
  495.      PyObject* self;
  496.      PyObject* args;
  497. {
  498.     PyObject* ast    = 0;
  499.     PyObject* tuple    = 0;
  500.     int          start_sym;
  501.     int          next_sym;
  502.  
  503.     if ((PyTuple_Size(args) == 1)
  504.     && (tuple = PyTuple_GetItem(args, 0))
  505.     && PyTuple_Check(tuple)
  506.     && (PyTuple_Size(tuple) >= 2)
  507.     && PyInt_Check(PyTuple_GetItem(tuple, 0))
  508.     && PyTuple_Check(PyTuple_GetItem(tuple, 1))
  509.     && (PyTuple_Size(PyTuple_GetItem(tuple, 1)) >= 2)
  510.     && PyInt_Check(PyTuple_GetItem(PyTuple_GetItem(tuple, 1), 0))) {
  511.  
  512.     /*
  513.      *  This might be a valid parse tree, but let's do a quick check
  514.      *  before we jump the gun.
  515.      */
  516.  
  517.     start_sym = PyInt_AsLong(PyTuple_GetItem(tuple, 0));
  518.     next_sym = PyInt_AsLong(PyTuple_GetItem(PyTuple_GetItem(tuple, 1), 0));
  519.  
  520.     if ((start_sym == eval_input) && (next_sym == testlist)) {
  521.         /*
  522.          *  Might be an expression.
  523.          */
  524.         node* expression = build_node_tree(PyTuple_GetItem(args, 0));
  525.  
  526.         puts("Parser.tuple2ast: built eval input tree.");
  527.         if ((expression != 0) && validate_expr_tree(expression))
  528.         ast = parser_newastobject(expression, PyAST_EXPR);
  529.     }
  530.     else if ((start_sym == file_input) && (next_sym == stmt)) {
  531.         /*
  532.          *  This looks like a suite so far.
  533.          */
  534.         node* suite_tree = build_node_tree(PyTuple_GetItem(args, 0));
  535.  
  536.         puts("Parser.tuple2ast: built file input tree.");
  537.         if ((suite_tree != 0) && validate_suite_tree(suite_tree))
  538.         ast = parser_newastobject(suite_tree, PyAST_SUITE);
  539.     }
  540.     /*
  541.      *  Make sure we throw an exception on all errors.  We should never
  542.      *  get this, but we'd do well to be sure something is done.
  543.      */
  544.     if ((ast == 0) && !PyErr_Occurred()) {
  545.         PyErr_SetString(parser_error, "Unspecified ast error occurred.");
  546.     }
  547.     }
  548.     else {
  549.     PyErr_SetString(PyExc_TypeError,
  550.             "parser.tuple2ast(): expected single tuple.");
  551.     }
  552.     return (ast);
  553.  
  554. }   /* parser_tuple2ast() */
  555.  
  556.  
  557. /*  int check_terminal_tuple()
  558.  *
  559.  *  Check a tuple to determine that it is indeed a valid terminal node.  The
  560.  *  node is known to be required as a terminal, so we throw an exception if
  561.  *  there is a failure.  The portion of the resulting node tree already built
  562.  *  is passed in so we can deallocate it in the event of a failure.
  563.  *
  564.  *  The format of an acceptable terminal tuple is "(is)":  the fact that elem
  565.  *  is a tuple and the integer is a valid terminal symbol has been established
  566.  *  before this function is called.  We must check the length of the tuple and
  567.  *  the type of the second element.  We do *NOT* check the actual text of the
  568.  *  string element, which we could do in many cases.  This is done by the
  569.  *  validate_*() functions which operate on the internal representation.
  570.  *
  571.  */
  572. static int
  573. check_terminal_tuple(elem, result)
  574.      PyObject* elem;
  575.      node*     result;
  576. {
  577.     int   res = 0;
  578.     char* str = 0;
  579.  
  580.     if (PyTuple_Size(elem) != 2) {
  581.     str = "Illegal terminal symbol; node too long.";
  582.     }
  583.     else if (!PyString_Check(PyTuple_GetItem(elem, 1))) {
  584.     str = "Illegal terminal symbol; expected a string.";
  585.     }
  586.     else
  587.     res = 1;
  588.  
  589.     if ((res == 0) && (result != 0)) {
  590.     elem = Py_BuildValue("(os)", elem, str);
  591.     PyErr_SetObject(parser_error, elem);
  592.     }
  593.     return (res);
  594.  
  595. }   /* check_terminal_tuple() */
  596.  
  597.  
  598. /*  node* build_node_children()
  599.  *
  600.  *  Iterate across the children of the current non-terminal node and build
  601.  *  their structures.  If successful, return the root of this portion of
  602.  *  the tree, otherwise, 0.  Any required exception will be specified already,
  603.  *  and no memory will have been deallocated.
  604.  *
  605.  */
  606. static node*
  607. build_node_children(tuple, root, line_num)
  608.      PyObject* tuple;
  609.      node*     root;
  610.      int*      line_num;
  611. {
  612.     int len = PyTuple_Size(tuple);
  613.     int i;
  614.  
  615.     for (i = 1; i < len; ++i) {
  616.     /* elem must always be a tuple, however simple */
  617.     PyObject* elem = PyTuple_GetItem(tuple, i);
  618.     long      type = 0;
  619.     char*     strn = 0;
  620.  
  621.     if ((!PyTuple_Check(elem)) || !PyInt_Check(PyTuple_GetItem(elem, 0))) {
  622.         PyErr_SetObject(parser_error,
  623.                 Py_BuildValue("(os)", elem,
  624.                       "Illegal node construct."));
  625.         return (0);
  626.     }
  627.     type = PyInt_AsLong(PyTuple_GetItem(elem, 0));
  628.  
  629.     if (ISTERMINAL(type)) {
  630.         if (check_terminal_tuple(elem, root))
  631.         strn = strdup(PyString_AsString(PyTuple_GetItem(elem, 1)));
  632.         else
  633.         return (0);
  634.     }
  635.     else if (!ISNONTERMINAL(type)) {
  636.         /*
  637.          *  It has to be one or the other; this is an error.
  638.          *  Throw an exception.
  639.          */
  640.         PyErr_SetObject(parser_error,
  641.                 Py_BuildValue("(os)", elem,
  642.                       "Unknown node type."));
  643.         return (0);
  644.     }
  645.     PyNode_AddChild(root, type, strn, *line_num);
  646.  
  647.     if (ISNONTERMINAL(type)) {
  648.         node* new_child = CHILD(root, i - 1);
  649.  
  650.         if (new_child != build_node_children(elem, new_child, line_num))
  651.         return (0);
  652.     }
  653.     else if (type == NEWLINE)    /* It's true:  we increment the     */
  654.         ++(*line_num);        /* line number *after* the newline! */
  655.     }
  656.     return (root);
  657.  
  658. }   /* build_node_children() */
  659.  
  660.  
  661. static node*
  662. build_node_tree(tuple)
  663.      PyObject* tuple;
  664. {
  665.     node* res = 0;
  666.     long  num = PyInt_AsLong(PyTuple_GetItem(tuple, 0));
  667.  
  668.     if (ISTERMINAL(num)) {
  669.     /*
  670.      *  The tuple is simple, but it doesn't start with a start symbol.
  671.      *  Throw an exception now and be done with it.
  672.      */
  673.     tuple = Py_BuildValue("(os)", tuple,
  674.                   "Illegal ast tuple; cannot start with terminal symbol.");
  675.     PyErr_SetObject(parser_error, tuple);
  676.     }
  677.     else if (ISNONTERMINAL(num)) {
  678.     /*
  679.      *  Not efficient, but that can be handled later.
  680.      */
  681.     int line_num = 0;
  682.  
  683.     res = PyNode_New(num);
  684.     if (res != build_node_children(tuple, res, &line_num)) {
  685.         PyNode_Free(res);
  686.         res = 0;
  687.     }
  688.     }
  689.     else {
  690.     /*
  691.      *  The tuple is illegal -- if the number is neither TERMINAL nor
  692.      *  NONTERMINAL, we can't use it.
  693.      */
  694.     PyErr_SetObject(parser_error,
  695.             Py_BuildValue("(os)", tuple,
  696.                       "Illegal component tuple."));
  697.     }
  698.     return (res);
  699.  
  700. }   /* build_node_tree() */
  701.  
  702.  
  703. #define    VALIDATER(n)    static int validate_##n(node*)
  704. #define    VALIDATE(n)    static int validate_##n(node* tree)
  705.  
  706.  
  707. /*
  708.  *  Validation for the code above:
  709.  */
  710. VALIDATER(expr_tree);
  711. VALIDATER(suite_tree);
  712.  
  713.  
  714. /*
  715.  *  Validation routines used within the validation section:
  716.  */
  717. staticforward int validate_terminal(node*, int, char*);
  718.  
  719. #define    validate_ampersand(ch)    validate_terminal(ch,       AMPER, "&")
  720. #define    validate_circumflex(ch)    validate_terminal(ch, CIRCUMFLEX, "^")
  721. #define validate_colon(ch)    validate_terminal(ch,       COLON, ":")
  722. #define validate_comma(ch)    validate_terminal(ch,       COMMA, ",")
  723. #define validate_dedent(ch)    validate_terminal(ch,      DEDENT, "")
  724. #define    validate_equal(ch)    validate_terminal(ch,       EQUAL, "=")
  725. #define validate_indent(ch)    validate_terminal(ch,      INDENT, "")
  726. #define validate_lparen(ch)    validate_terminal(ch,        LPAR, "(")
  727. #define    validate_newline(ch)    validate_terminal(ch,     NEWLINE, "")
  728. #define validate_rparen(ch)    validate_terminal(ch,        RPAR, ")")
  729. #define validate_semi(ch)    validate_terminal(ch,        SEMI, ";")
  730. #define    validate_star(ch)    validate_terminal(ch,        STAR, "*")
  731. #define    validate_vbar(ch)    validate_terminal(ch,        VBAR, "|")
  732.  
  733. #define    validate_compound_stmt(ch) validate_node(ch)
  734. #define    validate_name(ch, str)    validate_terminal(ch,    NAME, str)
  735. #define validate_small_stmt(ch)    validate_node(ch)
  736.  
  737. VALIDATER(class);        VALIDATER(node);
  738. VALIDATER(parameters);        VALIDATER(suite);
  739. VALIDATER(testlist);        VALIDATER(varargslist);
  740. VALIDATER(fpdef);        VALIDATER(fplist);
  741. VALIDATER(stmt);        VALIDATER(simple_stmt);
  742. VALIDATER(expr_stmt);
  743. VALIDATER(print_stmt);        VALIDATER(del_stmt);
  744. VALIDATER(return_stmt);
  745. VALIDATER(raise_stmt);        VALIDATER(import_stmt);
  746. VALIDATER(global_stmt);
  747. VALIDATER(access_stmt);        VALIDATER(accesstype);
  748. VALIDATER(exec_stmt);        VALIDATER(compound_stmt);
  749. VALIDATER(while);        VALIDATER(for);
  750. VALIDATER(try);            VALIDATER(except_clause);
  751. VALIDATER(test);        VALIDATER(and_test);
  752. VALIDATER(not_test);        VALIDATER(comparison);
  753. VALIDATER(comp_op);        VALIDATER(expr);
  754. VALIDATER(xor_expr);        VALIDATER(and_expr);
  755. VALIDATER(shift_expr);        VALIDATER(arith_expr);
  756. VALIDATER(term);        VALIDATER(factor);
  757. VALIDATER(atom);        VALIDATER(lambdef);
  758. VALIDATER(trailer);        VALIDATER(subscript);
  759. VALIDATER(exprlist);        VALIDATER(dictmaker);
  760.  
  761.  
  762. #define    is_even(n)    (((n) & 1) == 0)
  763. #define    is_odd(n)    (((n) & 1) == 1)
  764.  
  765.  
  766. static int
  767. validate_ntype(n, t)
  768.      node* n;
  769.      int   t;
  770. {
  771.     int res = (TYPE(n) == t);
  772.  
  773.     if (!res) {
  774.     char buffer[128];
  775.  
  776.     sprintf(buffer, "Expected node type %d, got %d.", t, TYPE(n));
  777.     PyErr_SetString(parser_error, buffer);
  778.     }
  779.     return (res);
  780.  
  781. }   /* validate_ntype() */
  782.  
  783.  
  784. static int
  785. validate_terminal(terminal, type, string)
  786.      node* terminal;
  787.      int   type;
  788.      char* string;
  789. {
  790.     static char buffer[60];
  791.     int res = ((TYPE(terminal) == type)
  792.            && (strcmp(string, STR(terminal)) == 0));
  793.  
  794.     if (!res) {
  795.     sprintf(buffer, "Illegal NAME: expected \"%s\"", string);
  796.     PyErr_SetString(parser_error, buffer);
  797.     }
  798.     return (res);
  799.  
  800. }   /* validate_terminal() */
  801.  
  802.  
  803. VALIDATE(class) {
  804.     int nch = NCH(tree);
  805.     int res = (((nch == 4)
  806.         || ((nch == 7)
  807.             && validate_lparen(CHILD(tree, 2))
  808.             && validate_ntype(CHILD(tree, 3), testlist)
  809.             && validate_testlist(CHILD(tree, 3))
  810.             && validate_rparen(CHILD(tree, 4))))
  811.         && validate_terminal(CHILD(tree, 0),    NAME, "class")
  812.         && validate_ntype(CHILD(tree, 1), NAME)
  813.         && validate_colon(CHILD(tree, nch - 2))
  814.         && validate_ntype(CHILD(tree, nch - 1), suite)
  815.         && validate_suite(CHILD(tree, nch - 1)));
  816.  
  817.     if (!res) {
  818.     if ((nch >= 2)
  819.         && validate_ntype(CHILD(tree, 1), NAME)) {
  820.         char buffer[128];
  821.  
  822.         sprintf(buffer, "Illegal classdef tuple for %s",
  823.             STR(CHILD(tree, 1)));
  824.         PyErr_SetString(parser_error, buffer);
  825.     }
  826.     else {
  827.         PyErr_SetString(parser_error, "Illegal classdef tuple.");
  828.     }
  829.     }
  830.     return (res);
  831.  
  832. }   /* validate_class() */
  833.  
  834.  
  835. static int
  836. validate_elif(elif_node, test_node, colon_node, suite_node)
  837.      node* elif_node;
  838.      node* test_node;
  839.      node* colon_node;
  840.      node* suite_node;
  841. {
  842.     return (validate_ntype(test_node, test)
  843.         && validate_ntype(suite_node, suite)
  844.         && validate_name(elif_node, "elif")
  845.         && validate_colon(colon_node)
  846.         && validate_node(test_node)
  847.         && validate_suite(suite_node));
  848.  
  849. }   /* validate_elif() */
  850.  
  851.  
  852. static int
  853. validate_else(else_node, colon_node, suite_node)
  854.      node* else_node;
  855.      node* colon_node;
  856.      node* suite_node;
  857. {
  858.     return (validate_ntype(suite_node, suite)
  859.         && validate_name(else_node, "else")
  860.         && validate_colon(colon_node)
  861.         && validate_suite(suite_node));
  862.  
  863. }   /* validate_else() */
  864.  
  865.  
  866. VALIDATE(if) {
  867.     int nch = NCH(tree);
  868.     int res = ((nch >= 4)
  869.            && validate_ntype(CHILD(tree, 1), test)
  870.            && validate_ntype(CHILD(tree, 3), suite)
  871.            && validate_name(CHILD(tree, 0), "if")
  872.            && validate_colon(CHILD(tree, 2))
  873.            && validate_parameters(CHILD(tree, 1))
  874.            && validate_suite(CHILD(tree, 3)));
  875.  
  876.     if (res && ((nch % 4) == 3)) {
  877.     /*
  878.      *  There must be a single 'else' clause, and maybe a series
  879.      *  of 'elif' clauses.
  880.      */
  881.     res = validate_else(CHILD(tree, nch-3), CHILD(tree, nch-2),
  882.                 CHILD(tree, nch-1));
  883.     nch -= 3;
  884.     }
  885.     if ((nch % 4) != 0)
  886.     res = 0;
  887.     else if (res && (nch > 4)) {
  888.     /*
  889.      *  There might be a series of 'elif' clauses.
  890.      */
  891.     int j = 4;
  892.     while ((j < nch) && res) {
  893.         res = validate_elif(CHILD(tree, j),   CHILD(tree, j+1),
  894.                 CHILD(tree, j+2), CHILD(tree, j+3));
  895.         j += 4;
  896.     }
  897.     }
  898.     if (!res && !PyErr_Occurred()) {
  899.     PyErr_SetString(parser_error, "Illegal 'if' statement found.");
  900.     }
  901.     return (res);
  902.  
  903. }   /* validate_if() */
  904.  
  905.  
  906. VALIDATE(parameters) {
  907.     int res = 1;
  908.     int nch = NCH(tree);
  909.  
  910.     res = (((nch == 2)
  911.         || ((nch == 3)
  912.         && validate_varargslist(CHILD(tree, 1))))
  913.        && validate_lparen(CHILD(tree, 0))
  914.        && validate_rparen(CHILD(tree, nch - 1)));
  915.  
  916.     return (res);
  917.  
  918. }   /* validate_parameters() */
  919.  
  920.  
  921. VALIDATE(suite) {
  922.     int res = 1;
  923.     int nch = NCH(tree);
  924.  
  925.     if (nch == 1) {
  926.     res = (validate_ntype(CHILD(tree, 0), simple_stmt)
  927.            && validate_simple_stmt(CHILD(tree, 0)));
  928.     }
  929.     else {
  930.     res = ((nch >= 5)
  931.            && validate_newline(CHILD(tree, 0))
  932.            && validate_indent(CHILD(tree, 1))
  933.            && validate_dedent(CHILD(tree, nch - 1)));
  934.  
  935.     if (res) {
  936.         int i = 2;
  937.  
  938.         while (TYPE(CHILD(tree, i)) == NEWLINE)
  939.         ++i;
  940.         res = (validate_ntype(CHILD(tree, i), stmt)
  941.            && validate_stmt(CHILD(tree, i)));
  942.  
  943.         if (res) {
  944.         ++i;
  945.         while (TYPE(CHILD(tree, i)) == NEWLINE)
  946.             ++i;
  947.  
  948.         while (res && (TYPE(CHILD(tree, i)) != DEDENT)) {
  949.             res = (validate_ntype(CHILD(tree, i), stmt)
  950.                && validate_stmt(CHILD(tree, i)));
  951.  
  952.             if (res) {
  953.             ++i;
  954.             while (TYPE(CHILD(tree, i)) == NEWLINE)
  955.                 ++i;
  956.             }
  957.         }
  958.         }
  959.     }
  960.     }
  961.     return (res);
  962.  
  963. }   /* validate_suite() */
  964.  
  965.  
  966. VALIDATE(testlist) {
  967.     int i;
  968.     int nch = NCH(tree);
  969.     int res = ((nch >= 1)
  970.            && (is_odd(nch)
  971.            || validate_comma(CHILD(tree, nch - 1))));
  972.  
  973.     /*
  974.      *    If there are an even, non-zero number of children, the last one
  975.      *    absolutely must be a comma.  Why the trailing comma is allowed,
  976.      *    I have no idea!
  977.      */
  978.     if ((res) && is_odd(nch)) {
  979.     /*
  980.      *  If the number is odd, the last is a test, and can be
  981.      *  verified.  What's left, if anything, can be verified
  982.      *  as a list of [test, comma] pairs.
  983.      */
  984.     --nch;
  985.     res = (validate_ntype(CHILD(tree, nch), test)
  986.            && validate_test(CHILD(tree, nch)));
  987.     }
  988.     for (i = 0; res && (i < nch); i += 2) {
  989.     res = (validate_ntype(CHILD(tree, i), test)
  990.            && validate_test(CHILD(tree, i))
  991.            && validate_comma(CHILD(tree, i + 1)));
  992.     }
  993.     return (res);
  994.  
  995. }   /* validate_testlist() */
  996.  
  997.  
  998. VALIDATE(varargslist) {
  999.     int nch = NCH(tree);
  1000.     int res = (nch != 0);
  1001.  
  1002.     if (res && (TYPE(CHILD(tree, 0)) == fpdef)) {
  1003.     int pos = 0;
  1004.  
  1005.     while (res && (pos < nch)) {
  1006.         res = (validate_ntype(CHILD(tree, pos), fpdef)
  1007.            && validate_fpdef(CHILD(tree, pos)));
  1008.         ++pos;
  1009.         if (res && (pos < nch) && (TYPE(CHILD(tree, pos)) == EQUAL)) {
  1010.         res = ((pos + 1 < nch)
  1011.                && validate_ntype(CHILD(tree, pos + 1), test)
  1012.                && validate_test(CHILD(tree, pos + 1)));
  1013.         pos += 2;
  1014.         }
  1015.         if (res && (pos < nch)) {
  1016.         res = validate_comma(CHILD(tree, pos));
  1017.         ++pos;
  1018.         }
  1019.     }
  1020.     }
  1021.     else {
  1022.     int pos = 0;
  1023.  
  1024.     res = ((nch > 1)
  1025.            && ((nch & 1) == 0)
  1026.            && validate_star(CHILD(tree, nch - 2))
  1027.            && validate_ntype(CHILD(tree, nch - 1), NAME));
  1028.  
  1029.     nch -= 2;
  1030.     while (res && (pos < nch)) {
  1031.         /*
  1032.          *  Sequence of:    fpdef ['=' test] ','
  1033.          */
  1034.         res = (validate_ntype(CHILD(tree, pos), fpdef)
  1035.            && validate_fpdef(CHILD(tree, pos))
  1036.            && ((TYPE(CHILD(tree, pos + 1)) == COMMA)
  1037.                || (((pos + 2) < nch)
  1038.                && validate_equal(CHILD(tree, pos + 1))
  1039.                && validate_ntype(CHILD(tree, pos + 2), test)
  1040.                && validate_test(CHILD(tree, pos + 2))
  1041.                && validate_comma(CHILD(tree, pos + 3)))));
  1042.     }
  1043.     }
  1044.     return (res);
  1045.  
  1046. }   /* validate_varargslist() */
  1047.  
  1048.  
  1049. VALIDATE(fpdef) {
  1050.     int nch = NCH(tree);
  1051.  
  1052.     return (((nch == 1)
  1053.          && validate_ntype(CHILD(tree, 0), NAME))
  1054.         || ((nch == 3)
  1055.         && validate_lparen(CHILD(tree, 0))
  1056.         && validate_fplist(CHILD(tree, 1))
  1057.         && validate_rparen(CHILD(tree, 2))));
  1058.  
  1059. } /* validate_fpdef() */
  1060.  
  1061.  
  1062. VALIDATE(fplist) {
  1063.     int j;
  1064.     int nch = NCH(tree);
  1065.     int res = ((nch != 0) && validate_fpdef(CHILD(tree, 0)));
  1066.  
  1067.     if (res && is_even(nch)) {
  1068.     res = validate_comma(CHILD(tree, nch - 1));
  1069.     --nch;
  1070.     }
  1071.     for (j = 1; res && (j < nch); j += 2) {
  1072.     res = (validate_comma(CHILD(tree, j))
  1073.            && validate_fpdef(CHILD(tree, j + 1)));
  1074.     }
  1075.     return (res);
  1076.  
  1077. }   /* validate_fplist() */
  1078.  
  1079.  
  1080. VALIDATE(stmt) {
  1081.     int nch = NCH(tree);
  1082.  
  1083.     return ((nch == 1)
  1084.         && (((TYPE(CHILD(tree, 0)) == simple_stmt)
  1085.          && validate_simple_stmt(CHILD(tree, 0)))
  1086.         || (validate_ntype(CHILD(tree, 0), compound_stmt)
  1087.             && validate_compound_stmt(CHILD(tree, 0)))));
  1088.  
  1089. }   /* validate_stmt() */
  1090.  
  1091.  
  1092. VALIDATE(simple_stmt) {
  1093.     int nch = NCH(tree);
  1094.     int res = ((nch >= 2)
  1095.            && validate_ntype(CHILD(tree, 0), small_stmt)
  1096.            && validate_small_stmt(CHILD(tree, 0))
  1097.            && validate_newline(CHILD(tree, nch - 1)));
  1098.  
  1099.     --nch;            /* forget the NEWLINE */
  1100.     if (res && (nch >= 2)) {
  1101.     if (TYPE(CHILD(tree, nch - 1)) == SEMI)
  1102.         --nch;
  1103.     }
  1104.     if (res && (nch > 2)) {
  1105.     int i;
  1106.  
  1107.     for (i = 1; res && (i < nch); i += 2) {
  1108.         res = (validate_semi(CHILD(tree, i))
  1109.            && validate_ntype(CHILD(tree, i + 1), small_stmt)
  1110.            && validate_small_stmt(CHILD(tree, i + 1)));
  1111.     }
  1112.     }
  1113.     return (res);
  1114.  
  1115. }   /* validate_simple_stmt() */
  1116.  
  1117.  
  1118. VALIDATE(expr_stmt) {
  1119.     int j;
  1120.     int nch = NCH(tree);
  1121.     int res = (is_odd(nch)
  1122.            && (validate_testlist(CHILD(tree, 0))));
  1123.  
  1124.     for (j = 1; res && (j < nch); j += 2) {
  1125.     res = (validate_equal(CHILD(tree, j))
  1126.            && validate_ntype(CHILD(tree, j + 1), testlist)
  1127.            && validate_testlist(CHILD(tree, j + 1)));
  1128.     }
  1129.     return (res);
  1130.  
  1131. }   /* validate_expr_stmt() */
  1132.  
  1133.  
  1134. VALIDATE(print_stmt) {
  1135.     int j;
  1136.     int nch = NCH(tree);
  1137.     int res = ((nch != 0)
  1138.            && is_even(nch)
  1139.            && validate_name(CHILD(tree, 0), "print")
  1140.            && validate_ntype(CHILD(tree, 1), test)
  1141.            && validate_test(CHILD(tree, 1)));
  1142.     
  1143.     for (j = 2; res && (j < nch); j += 2) {
  1144.     res = (validate_comma(CHILD(tree, j))
  1145.            && validate_ntype(CHILD(tree, j + 1), test)
  1146.            && validate_test(CHILD(tree, 1)));
  1147.     }
  1148.     return (res);
  1149.  
  1150. }   /* validate_print_stmt() */
  1151.  
  1152.  
  1153. VALIDATE(del_stmt) {
  1154.  
  1155.     return ((NCH(tree) == 2)
  1156.         && validate_name(CHILD(tree, 0), "del")
  1157.         && validate_ntype(CHILD(tree, 1), exprlist)
  1158.         && validate_exprlist(CHILD(tree, 1)));
  1159.  
  1160. }   /* validate_del_stmt() */
  1161.  
  1162.  
  1163. VALIDATE(return_stmt) {
  1164.     int nch = NCH(tree);
  1165.     int res = (((nch == 1)
  1166.         || (nch == 2))
  1167.            && validate_name(CHILD(tree, 0), "return"));
  1168.  
  1169.     if (res && (nch == 2)) {
  1170.     res = (validate_ntype(CHILD(tree, 1), testlist)
  1171.            && validate_testlist(CHILD(tree, 1)));
  1172.     }
  1173.     return (res);
  1174.  
  1175. }   /* validate_return_stmt() */
  1176.  
  1177.  
  1178. VALIDATE(raise_stmt) {
  1179.     int nch = NCH(tree);
  1180.     int res = (((nch == 2) || (nch == 4))
  1181.            && validate_name(CHILD(tree, 0), "raise")
  1182.            && validate_ntype(CHILD(tree, 1), test)
  1183.            && validate_test(CHILD(tree, 1)));
  1184.  
  1185.     if (res && (nch == 4)) {
  1186.     res = (validate_comma(CHILD(tree, 2))
  1187.            && (TYPE(CHILD(tree, 3)) == test)
  1188.            && validate_test(CHILD(tree, 3)));
  1189.     }
  1190.     return (res);
  1191.  
  1192. }   /* validate_raise_stmt() */
  1193.  
  1194.  
  1195. VALIDATE(import_stmt) {
  1196.     int nch = NCH(tree);
  1197.     int res = ((nch >= 2)
  1198.            && validate_ntype(CHILD(tree, 0), NAME)
  1199.            && validate_ntype(CHILD(tree, 1), NAME));
  1200.  
  1201.     if (res && (strcmp(STR(CHILD(tree, 0)), "import") == 0)) {
  1202.     res = is_even(nch);
  1203.     if (res) {
  1204.         int j;
  1205.  
  1206.         for (j = 2; res && (j < nch); j += 2) {
  1207.         res = (validate_comma(CHILD(tree, j))
  1208.                && validate_ntype(CHILD(tree, j + 1), NAME));
  1209.         }
  1210.     }
  1211.     }
  1212.     else if (res && validate_name(CHILD(tree, 0), "from")) {
  1213.     res = ((nch >= 4)
  1214.            && is_even(nch)
  1215.            && validate_name(CHILD(tree, 2), "import"));
  1216.     if (nch == 4) {
  1217.         res = ((TYPE(CHILD(tree, 3)) == NAME)
  1218.            || validate_ntype(CHILD(tree, 3), STAR));
  1219.     }
  1220.     else {
  1221.         /* 'from' NAME 'import' NAME (',' NAME)* */
  1222.         int j;
  1223.  
  1224.         res = validate_ntype(CHILD(tree, 3), NAME);
  1225.         for (j = 4; res && (j < nch); j += 2) {
  1226.         res = (validate_comma(CHILD(tree, j))
  1227.                && validate_ntype(CHILD(tree, j + 1), NAME));
  1228.         }
  1229.     }
  1230.     }
  1231.     else {
  1232.     res = 0;
  1233.     }
  1234.     return (res);
  1235.  
  1236. }   /* validate_import_stmt() */
  1237.  
  1238.  
  1239. VALIDATE(global_stmt) {
  1240.     int j;
  1241.     int nch = NCH(tree);
  1242.     int res = (is_even(nch)
  1243.            && validate_name(CHILD(tree, 0), "global")
  1244.            && validate_ntype(CHILD(tree, 1), NAME));
  1245.  
  1246.     for (j = 2; res && (j < nch); j += 2) {
  1247.     res = (validate_comma(CHILD(tree, j))
  1248.            && validate_ntype(CHILD(tree, j + 1), NAME));
  1249.     }
  1250.     return (res);
  1251.  
  1252. }   /* validate_global_stmt() */
  1253.  
  1254.  
  1255. VALIDATE(access_stmt) {
  1256.     int pos = 3;
  1257.     int nch = NCH(tree);
  1258.     int res = ((nch >= 4)
  1259.            && is_even(nch)
  1260.            && validate_name(CHILD(tree, 0), "access")
  1261.            && validate_accesstype(CHILD(tree, nch - 1)));
  1262.  
  1263.     if (res && (TYPE(CHILD(tree, 1)) != STAR)) {
  1264.     int j;
  1265.  
  1266.     res = validate_ntype(CHILD(tree, 1), NAME);
  1267.     for (j = 2; res && (j < (nch - 2)); j += 2) {
  1268.         if (TYPE(CHILD(tree, j)) == COLON)
  1269.         break;
  1270.         res = (validate_comma(CHILD(tree, j))
  1271.            && validate_ntype(CHILD(tree, j + 1), NAME)
  1272.            && (pos += 2));
  1273.     }
  1274.     }
  1275.     else {
  1276.     res = validate_star(CHILD(tree, 1));
  1277.     }
  1278.     res = (res && validate_colon(CHILD(tree, pos - 1)));
  1279.  
  1280.     for (; res && (pos < (nch - 1)); pos += 2) {
  1281.     res = (validate_accesstype(CHILD(tree, pos))
  1282.            && validate_comma(CHILD(tree, pos + 1)));
  1283.     }
  1284.     return (res && (pos == (nch - 1)));
  1285.  
  1286. }   /* validate_access_stmt() */
  1287.  
  1288.  
  1289. VALIDATE(accesstype) {
  1290.     int nch = NCH(tree);
  1291.     int res = (nch >= 1);
  1292.     int i;
  1293.  
  1294.     for (i = 0; res && (i < nch); ++i) {
  1295.     res = validate_ntype(CHILD(tree, i), NAME);
  1296.     }
  1297.     return (res);
  1298.  
  1299. }   /* validate_accesstype() */
  1300.  
  1301.  
  1302. VALIDATE(exec_stmt) {
  1303.     int nch = NCH(tree);
  1304.     int res = (((nch == 2) || (nch == 4) || (nch == 6))
  1305.            && validate_name(CHILD(tree, 0), "exec")
  1306.            && validate_expr(CHILD(tree, 1)));
  1307.  
  1308.     if (res && (nch > 2)) {
  1309.     res = (validate_name(CHILD(tree, 2), "in")
  1310.            && validate_test(CHILD(tree, 3)));
  1311.     }
  1312.     if (res && (nch > 4)) {
  1313.     res = (validate_comma(CHILD(tree, 4))
  1314.            && validate_test(CHILD(tree, 5)));
  1315.     }
  1316.     return (res);
  1317.  
  1318. }   /* validate_exec_stmt() */
  1319.  
  1320.  
  1321. VALIDATE(while) {
  1322.     int nch = NCH(tree);
  1323.     int res = (((nch == 4) || (nch == 7))
  1324.            && validate_name(CHILD(tree, 0), "while")
  1325.            && validate_ntype(CHILD(tree, 1), test)
  1326.            && validate_test(CHILD(tree, 1))
  1327.            && validate_colon(CHILD(tree, 2))
  1328.            && validate_ntype(CHILD(tree, 3), suite)
  1329.            && validate_suite(CHILD(tree, 3)));
  1330.  
  1331.     if (res && (nch == 7)) {
  1332.     res = (validate_name(CHILD(tree, 4), "else")
  1333.            && validate_colon(CHILD(tree, 5))
  1334.            && validate_ntype(CHILD(tree, 6), suite)
  1335.            && validate_suite(CHILD(tree, 6)));
  1336.     }
  1337.     return (res);
  1338.  
  1339. }   /* validate_while() */
  1340.  
  1341.  
  1342. VALIDATE(for) {
  1343.     int nch = NCH(tree);
  1344.     int res = (((nch == 6) || (nch == 9))
  1345.            && validate_name(CHILD(tree, 0), "for")
  1346.            && validate_ntype(CHILD(tree, 1), exprlist)
  1347.            && validate_exprlist(CHILD(tree, 1))
  1348.            && validate_name(CHILD(tree, 2), "in")
  1349.            && validate_ntype(CHILD(tree, 3), testlist)
  1350.            && validate_testlist(CHILD(tree, 3))
  1351.            && validate_colon(CHILD(tree, 4))
  1352.            && validate_ntype(CHILD(tree, 5), suite)
  1353.            && validate_suite(CHILD(tree, 5)));
  1354.  
  1355.     if (res && (nch == 9)) {
  1356.     res = (validate_name(CHILD(tree, 6), "else")
  1357.            && validate_colon(CHILD(tree, 7))
  1358.            && validate_ntype(CHILD(tree, 8), suite)
  1359.            && validate_suite(CHILD(tree, 8)));
  1360.     }
  1361.     return (res);
  1362.  
  1363. }   /* validate_for() */
  1364.  
  1365.  
  1366. VALIDATE(try) {
  1367.     int nch = NCH(tree);
  1368.     int res = ((nch >= 6)
  1369.            && ((nch % 3) == 0)
  1370.            && validate_name(CHILD(tree, 0), "try")
  1371.            && validate_colon(CHILD(tree, 1))
  1372.            && validate_ntype(CHILD(tree, 2), suite)
  1373.            && validate_suite(CHILD(tree, 2))
  1374.            && validate_colon(CHILD(tree, nch - 2))
  1375.            && validate_ntype(CHILD(tree, nch - 1), suite)
  1376.            && validate_suite(CHILD(tree, nch - 1)));
  1377.  
  1378.     if (res && (TYPE(CHILD(tree, 3)) == except_clause)) {
  1379.     int groups = (nch / 3) - 2;
  1380.  
  1381.     res = validate_except_clause(CHILD(tree, 3));
  1382.  
  1383.     if (res && (groups != 0)) {
  1384.         int cln_pos = 4;
  1385.         int sui_pos = 5;
  1386.         int nxt_pos = 6;
  1387.  
  1388.         while (res && groups--) {
  1389.         res = (validate_colon(CHILD(tree, cln_pos))
  1390.                && validate_ntype(CHILD(tree, sui_pos), suite)
  1391.                && validate_suite(CHILD(tree, sui_pos)));
  1392.  
  1393.         if (res && (TYPE(CHILD(tree, nxt_pos)) == NAME)) {
  1394.             res = ((groups == 0)
  1395.                && validate_name(CHILD(tree, nxt_pos), "else"));
  1396.         }
  1397.         else if (res) {
  1398.             res = (validate_ntype(CHILD(tree, nxt_pos), except_clause)
  1399.                && validate_except_clause(CHILD(tree, nxt_pos)));
  1400.         }
  1401.         /* Update for next group. */
  1402.         cln_pos += 3;
  1403.         sui_pos += 3;
  1404.         nxt_pos += 3;
  1405.         }
  1406.     }
  1407.     }
  1408.     else if (res) {
  1409.     res = ((nch == 6)
  1410.            && validate_name(CHILD(tree, 3), "finally"));
  1411.     }
  1412.     return (res);
  1413.  
  1414. }   /* validate_try() */
  1415.  
  1416.  
  1417. VALIDATE(except_clause) {
  1418.     int nch = NCH(tree);
  1419.     int res = (((nch == 1) || (nch == 2) || (nch == 4))
  1420.            && validate_name(CHILD(tree, 0), "except"));
  1421.  
  1422.     if (res && (nch > 1)) {
  1423.     res = (validate_ntype(CHILD(tree, 1), test)
  1424.            && validate_test(CHILD(tree, 1)));
  1425.     }
  1426.     if (res && (nch == 4)) {
  1427.     res = (validate_comma(CHILD(tree, 2))
  1428.            && validate_ntype(CHILD(tree, 3), test)
  1429.            && validate_test(CHILD(tree, 3)));
  1430.     }
  1431.     return (res);
  1432.  
  1433. }   /* validate_except_clause() */
  1434.  
  1435.  
  1436. VALIDATE(test) {
  1437.     int nch = NCH(tree);
  1438.     int res = is_odd(nch);
  1439.  
  1440.     if (res && (TYPE(CHILD(tree, 0)) == lambdef)) {
  1441.     res = ((nch == 1)
  1442.            && validate_lambdef(CHILD(tree, 0)));
  1443.     }
  1444.     else if (res) {
  1445.     int pos;
  1446.  
  1447.     res = (validate_ntype(CHILD(tree, 0), and_test)
  1448.            && validate_and_test(CHILD(tree, 0)));
  1449.  
  1450.     for (pos = 1; res && (pos < nch); pos += 2) {
  1451.         res = (validate_comma(CHILD(tree, pos))
  1452.            && validate_ntype(CHILD(tree, pos + 1), and_test)
  1453.            && validate_and_test(CHILD(tree, pos + 1)));
  1454.     }
  1455.     }
  1456.     return (res);
  1457.  
  1458. }   /* validate_test() */
  1459.  
  1460.  
  1461. VALIDATE(and_test) {
  1462.     int pos;
  1463.     int nch = NCH(tree);
  1464.     int res = (is_odd(nch)
  1465.            && validate_ntype(CHILD(tree, 0), not_test)
  1466.            && validate_not_test(CHILD(tree, 0)));
  1467.  
  1468.     for (pos = 1; res && (pos < nch); pos += 2) {
  1469.     res = (validate_name(CHILD(tree, pos), "and")
  1470.            && validate_ntype(CHILD(tree, 0), not_test)
  1471.            && validate_not_test(CHILD(tree, 0)));
  1472.     }
  1473.     return (res);
  1474.  
  1475. }   /* validate_and_test() */
  1476.  
  1477.  
  1478. VALIDATE(not_test) {
  1479.     int nch = NCH(tree);
  1480.  
  1481.     return (((nch == 2)
  1482.          && validate_name(CHILD(tree, 0), "not")
  1483.          && validate_ntype(CHILD(tree, 1), not_test)
  1484.          && validate_not_test(CHILD(tree, 1)))
  1485.         || ((nch == 1)
  1486.         && validate_ntype(CHILD(tree, 0), comparison)
  1487.         && validate_comparison(CHILD(tree, 0))));
  1488.  
  1489. }   /* validate_not_test() */
  1490.  
  1491.  
  1492. VALIDATE(comparison) {
  1493.     int pos;
  1494.     int nch = NCH(tree);
  1495.     int res = (is_odd(nch)
  1496.            && validate_ntype(CHILD(tree, 0), expr)
  1497.            && validate_expr(CHILD(tree, 0)));
  1498.  
  1499.     for (pos = 1; res && (pos < nch); pos += 2) {
  1500.     res = (validate_ntype(CHILD(tree, pos), comp_op)
  1501.            && validate_comp_op(CHILD(tree, pos))
  1502.            && validate_ntype(CHILD(tree, pos + 1), expr)
  1503.            && validate_expr(CHILD(tree, 1)));
  1504.     }
  1505.     return (res);
  1506.  
  1507. }   /* validate_comparison() */
  1508.  
  1509.  
  1510. VALIDATE(comp_op) {
  1511.     int res = 0;
  1512.     int nch = NCH(tree);
  1513.  
  1514.     if (nch == 1) {
  1515.     /*
  1516.      *  Only child will be a terminal with a well-defined symbolic name
  1517.      *  or a NAME with a string of either 'is' or 'in'
  1518.      */
  1519.     tree = CHILD(tree, 0);
  1520.     switch (TYPE(tree)) {
  1521.         case LESS:
  1522.         case GREATER:
  1523.         case EQEQUAL:
  1524.         case EQUAL:
  1525.         case LESSEQUAL:
  1526.         case GREATEREQUAL:
  1527.         case NOTEQUAL:
  1528.           res = 1;
  1529.           break;
  1530.         case NAME:
  1531.           res = ((strcmp(STR(tree), "in") == 0)
  1532.              || (strcmp(STR(tree), "is") == 0));
  1533.           if (!res) {
  1534.           char buffer[128];
  1535.  
  1536.           sprintf(buffer, "Illegal comparison operator: '%s'.",
  1537.               STR(tree));
  1538.           PyErr_SetString(parser_error, buffer);
  1539.           }
  1540.           break;
  1541.       default:
  1542.           PyErr_SetString(parser_error,
  1543.                   "Illegal comparison operator type.");
  1544.           break;
  1545.     }
  1546.     }
  1547.     else if (nch == 2) {
  1548.     res = (validate_ntype(CHILD(tree, 0), NAME)
  1549.            && validate_ntype(CHILD(tree, 1), NAME)
  1550.            && (((strcmp(STR(CHILD(tree, 0)), "is") == 0)
  1551.             && (strcmp(STR(CHILD(tree, 1)), "not") == 0))
  1552.            || ((strcmp(STR(CHILD(tree, 0)), "not") == 0)
  1553.                && (strcmp(STR(CHILD(tree, 1)), "in") == 0))));
  1554.     }
  1555.  
  1556.     if (!res && !PyErr_Occurred()) {
  1557.     PyErr_SetString(parser_error, "Unknown comparison operator.");
  1558.     }
  1559.     return (res);
  1560.  
  1561. }   /* validate_comp_op() */
  1562.  
  1563.  
  1564. VALIDATE(expr) {
  1565.     int j;
  1566.     int nch = NCH(tree);
  1567.     int res = (is_odd(nch)
  1568.            && validate_ntype(CHILD(tree, 0), xor_expr)
  1569.            && validate_xor_expr(CHILD(tree, 0)));
  1570.  
  1571.     for (j = 2; res && (j < nch); j += 2) {
  1572.     res = (validate_ntype(CHILD(tree, j), xor_expr)
  1573.            && validate_xor_expr(CHILD(tree, j))
  1574.            && validate_vbar(CHILD(tree, j - 1)));
  1575.     }
  1576.     return (res);
  1577.  
  1578. }   /* validate_expr() */
  1579.  
  1580.  
  1581. VALIDATE(xor_expr) {
  1582.     int j;
  1583.     int nch = NCH(tree);
  1584.     int res = (is_odd(nch)
  1585.            && validate_ntype(CHILD(tree, 0), and_expr)
  1586.            && validate_and_expr(CHILD(tree, 0)));
  1587.  
  1588.     for (j = 2; res && (j < nch); j += 2) {
  1589.     res = (validate_circumflex(CHILD(tree, j - 1))
  1590.            && validate_ntype(CHILD(tree, j), and_expr)
  1591.            && validate_and_expr(CHILD(tree, j)));
  1592.     }
  1593.     return (res);
  1594.  
  1595. }   /* validate_xor_expr() */
  1596.  
  1597.  
  1598. VALIDATE(and_expr) {
  1599.     int pos;
  1600.     int nch = NCH(tree);
  1601.     int res = (is_odd(nch)
  1602.            && validate_ntype(CHILD(tree, 0), shift_expr)
  1603.            && validate_shift_expr(CHILD(tree, 0)));
  1604.  
  1605.     for (pos = 1; res && (pos < nch); pos += 2) {
  1606.     res = (validate_ampersand(CHILD(tree, pos))
  1607.            && validate_ntype(CHILD(tree, pos + 1), shift_expr)
  1608.            && validate_shift_expr(CHILD(tree, pos + 1)));
  1609.     }
  1610.     return (res);
  1611.  
  1612. }   /* validate_and_expr() */
  1613.  
  1614.  
  1615. static int
  1616. validate_chain_two_ops(tree, termtype, termvalid, op1, op2)
  1617.      node*    tree;
  1618.      int    termtype;
  1619.      int (*termvalid)(node*);
  1620.      int    op1, op2;
  1621. {
  1622.     int pos;
  1623.     int nch = NCH(tree);
  1624.     int res = (is_odd(nch)
  1625.            && validate_ntype(CHILD(tree, 0), termtype)
  1626.            && (*termvalid)(CHILD(tree, 0)));
  1627.  
  1628.     for (pos = 1; res && (pos < nch); pos += 2) {
  1629.     res = (((TYPE(CHILD(tree, pos)) == op1)
  1630.         || validate_ntype(CHILD(tree, pos), op2))
  1631.            && validate_ntype(CHILD(tree, pos + 1), termtype)
  1632.            && (*termvalid)(CHILD(tree, pos + 1)));
  1633.     }
  1634.     return (res);
  1635.  
  1636. }   /* validate_chain_two_ops() */
  1637.  
  1638.  
  1639. VALIDATE(shift_expr) {
  1640.  
  1641.     return (validate_chain_two_ops(tree, arith_expr,
  1642.                    validate_arith_expr,
  1643.                    LEFTSHIFT, RIGHTSHIFT));
  1644.  
  1645. }   /* validate_shift_expr() */
  1646.  
  1647.  
  1648. VALIDATE(arith_expr) {
  1649.  
  1650.     return (validate_chain_two_ops(tree, term,
  1651.                    validate_term,
  1652.                    PLUS, MINUS));
  1653.  
  1654. }   /* validate_arith_expr() */
  1655.  
  1656.  
  1657. VALIDATE(term) {
  1658.     int pos;
  1659.     int nch = NCH(tree);
  1660.     int res = (is_odd(nch)
  1661.            && validate_ntype(CHILD(tree, 0), factor)
  1662.            && validate_factor(CHILD(tree, 0)));
  1663.  
  1664.     for (pos = 1; res && (pos < nch); pos += 2) {
  1665.     res= (((TYPE(CHILD(tree, pos)) == STAR)
  1666.            || (TYPE(CHILD(tree, pos)) == SLASH)
  1667.            || validate_ntype(CHILD(tree, pos), PERCENT))
  1668.           && validate_ntype(CHILD(tree, pos + 1), factor)
  1669.           && validate_factor(CHILD(tree, pos + 1)));
  1670.     }
  1671.     return (res);
  1672.  
  1673. }   /* validate_term() */
  1674.  
  1675.  
  1676. VALIDATE(factor) {
  1677.     int nch = NCH(tree);
  1678.     int res = (((nch == 2)
  1679.         && ((TYPE(CHILD(tree, 0)) == PLUS)
  1680.             || (TYPE(CHILD(tree, 0)) == MINUS)
  1681.             || validate_ntype(CHILD(tree, 0), TILDE))
  1682.         && validate_ntype(CHILD(tree, 1), factor)
  1683.         && validate_factor(CHILD(tree, 1)))
  1684.            || ((nch >= 1)
  1685.            && validate_ntype(CHILD(tree, 0), atom)
  1686.            && validate_atom(CHILD(tree, 0))));
  1687.  
  1688.     if (res && (TYPE(CHILD(tree, 0)) == atom)) {
  1689.     int pos;
  1690.  
  1691.     for (pos = 1; res && (pos < nch); ++pos) {
  1692.         res = (validate_ntype(CHILD(tree, pos), trailer)
  1693.            && validate_trailer(CHILD(tree, pos)));
  1694.     }
  1695.     }
  1696.     return (res);
  1697.  
  1698. }   /* validate_factor() */
  1699.  
  1700.  
  1701. VALIDATE(atom) {
  1702.     int pos;
  1703.     int nch = NCH(tree);
  1704.     int res = (nch >= 1);
  1705.  
  1706.     if (res) {
  1707.     switch (TYPE(CHILD(tree, 0))) {
  1708.       case LPAR:
  1709.         res = ((nch <= 3)
  1710.            && (validate_rparen(CHILD(tree, nch - 1))));
  1711.  
  1712.         if (res && (nch == 3)) {
  1713.         res = (validate_ntype(CHILD(tree, 1), testlist)
  1714.                && validate_testlist(CHILD(tree, 1)));
  1715.         }
  1716.         break;
  1717.       case LSQB:
  1718.         res = ((nch <= 3)
  1719.            && validate_ntype(CHILD(tree, nch - 1), RSQB));
  1720.  
  1721.         if (res && (nch == 3)) {
  1722.         res = (validate_ntype(CHILD(tree, 1), testlist)
  1723.                && validate_testlist(CHILD(tree, 1)));
  1724.         }
  1725.         break;
  1726.       case LBRACE:
  1727.         res = ((nch <= 3)
  1728.            && validate_ntype(CHILD(tree, nch - 1), RBRACE));
  1729.  
  1730.         if (res && (nch == 3)) {
  1731.         res = (validate_ntype(CHILD(tree, 1), dictmaker)
  1732.                && validate_dictmaker(CHILD(tree, 1)));
  1733.         }
  1734.         break;
  1735.       case BACKQUOTE:
  1736.         res = ((nch == 3)
  1737.            && validate_ntype(CHILD(tree, 1), testlist)
  1738.            && validate_testlist(CHILD(tree, 1))
  1739.            && validate_ntype(CHILD(tree, 2), BACKQUOTE));
  1740.         break;
  1741.       case NAME:
  1742.       case NUMBER:
  1743.         res = (nch == 1);
  1744.         break;
  1745.       case STRING:
  1746.         for (pos = 1; res && (pos < nch); ++pos) {
  1747.         res = validate_ntype(CHILD(tree, pos), STRING);
  1748.         }
  1749.         break;
  1750.       default:
  1751.         res = 0;
  1752.         break;
  1753.     }
  1754.     }
  1755.     return (res);
  1756.  
  1757. }   /* validate_atom() */
  1758.  
  1759.  
  1760. VALIDATE(funcdef) {
  1761.  
  1762.     return ((NCH(tree) == 5)
  1763.         && validate_name(CHILD(tree, 0), "def")
  1764.         && validate_ntype(CHILD(tree, 1), NAME)
  1765.         && validate_ntype(CHILD(tree, 2), parameters)
  1766.         && validate_colon(CHILD(tree, 3))
  1767.         && validate_ntype(CHILD(tree, 4), suite)
  1768.         && validate_parameters(CHILD(tree, 2))
  1769.         && validate_suite(CHILD(tree, 4)));
  1770.  
  1771. }   /* validate_funcdef() */
  1772.  
  1773.  
  1774. VALIDATE(lambdef) {
  1775.     int nch = NCH(tree);
  1776.     int res = (((nch == 3) || (nch == 4))
  1777.            && validate_name(CHILD(tree, 0), "lambda")
  1778.            && validate_colon(CHILD(tree, nch - 2))
  1779.            && validate_ntype(CHILD(tree, nch - 1), test)
  1780.            && validate_testlist(CHILD(tree, nch - 1)));
  1781.  
  1782.     if (res && (nch == 4)) {
  1783.     res = (validate_ntype(CHILD(tree, 1), varargslist)
  1784.            && validate_varargslist(CHILD(tree, 1)));
  1785.     }
  1786.     return (res);
  1787.  
  1788. }   /* validate_lambdef() */
  1789.  
  1790.  
  1791. VALIDATE(trailer) {
  1792.     int nch = NCH(tree);
  1793.     int res = ((nch == 2) || (nch == 3));
  1794.  
  1795.     if (res) {
  1796.     switch (TYPE(CHILD(tree, 0))) {
  1797.       case LPAR:
  1798.         res = validate_rparen(CHILD(tree, nch - 1));
  1799.         if (res && (nch == 3)) {
  1800.         res = (validate_ntype(CHILD(tree, 1), testlist)
  1801.                && validate_testlist(CHILD(tree, 1)));
  1802.         }
  1803.         break;
  1804.       case LSQB:
  1805.         res = ((nch == 3)
  1806.            && validate_ntype(CHILD(tree, 1), subscript)
  1807.            && validate_subscript(CHILD(tree, 1))
  1808.            && validate_ntype(CHILD(tree, 2), RSQB));
  1809.         break;
  1810.       case DOT:
  1811.         res = ((nch == 2)
  1812.            && validate_ntype(CHILD(tree, 1), NAME));
  1813.         break;
  1814.       default:
  1815.         res = 0;
  1816.         break;
  1817.     }
  1818.     }
  1819.     return (res);
  1820.  
  1821. }   /* validate_trailer() */
  1822.  
  1823.  
  1824. VALIDATE(subscript) {
  1825.     int nch = NCH(tree);
  1826.     int res = ((nch >= 1) && (nch <= 3));
  1827.  
  1828.     if (res && is_odd(nch)) {
  1829.     res = (validate_ntype(CHILD(tree, 0), test)
  1830.            && validate_test(CHILD(tree, 0)));
  1831.  
  1832.     if (res && (nch == 3)) {
  1833.         res = (validate_colon(CHILD(tree, 1))
  1834.            && validate_ntype(CHILD(tree, 2), test)
  1835.            && validate_test(CHILD(tree, 2)));
  1836.     }
  1837.     }
  1838.     else if (res == 2) {
  1839.     if (TYPE(CHILD(tree, 0)) == COLON) {
  1840.         res = (validate_ntype(CHILD(tree, 1), test)
  1841.            && validate_test(CHILD(tree, 1)));
  1842.     }
  1843.     else {
  1844.         res = (validate_ntype(CHILD(tree, 0), test)
  1845.            && validate_test(CHILD(tree, 0))
  1846.            && validate_colon(CHILD(tree, 1)));
  1847.     }
  1848.     }
  1849.     return (res);
  1850.  
  1851. }   /* validate_subscript() */
  1852.  
  1853.  
  1854. VALIDATE(exprlist) {
  1855.     int nch = NCH(tree);
  1856.     int res = ((nch >= 1)
  1857.            && validate_ntype(CHILD(tree, 0), expr)
  1858.            && validate_expr(CHILD(tree, 0)));
  1859.  
  1860.     if (res && is_even(nch)) {
  1861.     res = validate_comma(CHILD(tree, --nch));
  1862.     }
  1863.     if (res && (nch > 1)) {
  1864.     int pos;
  1865.  
  1866.     for (pos = 1; res && (pos < nch); pos += 2) {
  1867.         res = (validate_comma(CHILD(tree, pos))
  1868.            && validate_ntype(CHILD(tree, pos + 1), expr)
  1869.            && validate_expr(CHILD(tree, pos + 1)));
  1870.     }
  1871.     }
  1872.     return (res);
  1873.  
  1874. }   /* validate_exprlist() */
  1875.  
  1876.  
  1877. VALIDATE(dictmaker) {
  1878.     int nch = NCH(tree);
  1879.     int res = ((nch >= 3)
  1880.            && validate_ntype(CHILD(tree, 0), test)
  1881.            && validate_test(CHILD(tree, 0))
  1882.            && validate_colon(CHILD(tree, 1))
  1883.            && validate_ntype(CHILD(tree, 2), test)
  1884.            && validate_test(CHILD(tree, 2)));
  1885.  
  1886.     if (res && ((nch % 4) == 0)) {
  1887.     res = validate_comma(CHILD(tree, --nch));
  1888.     }
  1889.     else if (res) {
  1890.     res = ((nch % 4) == 3);
  1891.     }
  1892.     if (res && (nch > 3)) {
  1893.     int pos = 3;
  1894.  
  1895.     /* What's left are groups of:  ',' test ':' test  */
  1896.     while (res && (pos < nch)) {
  1897.         res = (validate_comma(CHILD(tree, pos))
  1898.            && validate_ntype(CHILD(tree, pos + 1), test)
  1899.            && validate_test(CHILD(tree, pos + 1))
  1900.            && validate_colon(CHILD(tree, pos + 2))
  1901.            && validate_ntype(CHILD(tree, pos + 3), test)
  1902.            && validate_test(CHILD(tree, pos + 3)));
  1903.         pos += 4;
  1904.     }
  1905.     }
  1906.     return (res);
  1907.  
  1908. }   /* validate_dictmaker() */
  1909.  
  1910.  
  1911. VALIDATE(eval_input) {
  1912.     int pos;
  1913.     int nch = NCH(tree);
  1914.     int res = ((nch >= 2)
  1915.            && validate_testlist(CHILD(tree, 0))
  1916.            && validate_ntype(CHILD(tree, nch - 1), ENDMARKER));
  1917.  
  1918.     for (pos = 1; res && (pos < (nch - 1)); ++pos) {
  1919.     res = validate_ntype(CHILD(tree, pos), NEWLINE);
  1920.     }
  1921.     return (res);
  1922.  
  1923. }   /* validate_eval_input() */
  1924.  
  1925.  
  1926. VALIDATE(node) {
  1927.     int   nch  = 0;            /* num. children on current node  */
  1928.     int   res  = 1;            /* result value              */
  1929.     node* next = 0;            /* node to process after this one */
  1930.     
  1931.     while (res & (tree != 0)) {
  1932.     nch  = NCH(tree);
  1933.     next = 0;
  1934.     switch (TYPE(tree)) {
  1935.         /*
  1936.          *  Definition nodes.
  1937.          */
  1938.       case funcdef:
  1939.         res = validate_funcdef(tree);
  1940.         break;
  1941.       case classdef:
  1942.         res = validate_class(tree);
  1943.         break;
  1944.         /*
  1945.          *  "Trivial" parse tree nodes.
  1946.          */
  1947.       case stmt:
  1948.         res = validate_stmt(tree);
  1949.         break;
  1950.       case small_stmt:
  1951.         res = ((nch == 1)
  1952.            && ((TYPE(CHILD(tree, 0)) == expr_stmt)
  1953.                || (TYPE(CHILD(tree, 0)) == print_stmt)
  1954.                || (TYPE(CHILD(tree, 0)) == del_stmt)
  1955.                || (TYPE(CHILD(tree, 0)) == pass_stmt)
  1956.                || (TYPE(CHILD(tree, 0)) == flow_stmt)
  1957.                || (TYPE(CHILD(tree, 0)) == import_stmt)
  1958.                || (TYPE(CHILD(tree, 0)) == global_stmt)
  1959.                || (TYPE(CHILD(tree, 0)) == access_stmt)
  1960.                || validate_ntype(CHILD(tree, 0), exec_stmt))
  1961.            && (next = CHILD(tree, 0)));
  1962.         break;
  1963.       case flow_stmt:
  1964.         res  = ((nch == 1)
  1965.             && ((TYPE(CHILD(tree, 0)) == break_stmt)
  1966.             || (TYPE(CHILD(tree, 0)) == continue_stmt)
  1967.             || (TYPE(CHILD(tree, 0)) == return_stmt)
  1968.             || validate_ntype(CHILD(tree, 0), raise_stmt))
  1969.             && (next = CHILD(tree, 0)));
  1970.         break;
  1971.         /*
  1972.          *  Compound statements.
  1973.          */
  1974.       case simple_stmt:
  1975.         res = validate_simple_stmt(tree);
  1976.         break;
  1977.       case compound_stmt:
  1978.         res = ((NCH(tree) == 1)
  1979.            && ((TYPE(CHILD(tree, 0)) == if_stmt)
  1980.                || (TYPE(CHILD(tree, 0)) == while_stmt)
  1981.                || (TYPE(CHILD(tree, 0)) == for_stmt)
  1982.                || (TYPE(CHILD(tree, 0)) == try_stmt)
  1983.                || (TYPE(CHILD(tree, 0)) == funcdef)
  1984.                || validate_ntype(CHILD(tree, 0), classdef))
  1985.            && (next = CHILD(tree, 0)));
  1986.         break;
  1987.         /*
  1988.          *  Fundemental statements.
  1989.          */
  1990.       case expr_stmt:
  1991.         res = validate_expr_stmt(tree);
  1992.         break;
  1993.       case print_stmt:
  1994.         res = validate_print_stmt(tree);
  1995.         break;
  1996.       case del_stmt:
  1997.         res = validate_del_stmt(tree);
  1998.         break;
  1999.       case pass_stmt:
  2000.         res = ((nch == 1)
  2001.            && validate_name(CHILD(tree, 0), "pass"));
  2002.         break;
  2003.       case break_stmt:
  2004.         res = ((nch == 1)
  2005.            && validate_name(CHILD(tree, 0), "break"));
  2006.         break;
  2007.       case continue_stmt:
  2008.         res = ((nch == 1)
  2009.            && validate_name(CHILD(tree, 0), "continue"));
  2010.         break;
  2011.       case return_stmt:
  2012.         res = validate_return_stmt(tree);
  2013.         break;
  2014.       case raise_stmt:
  2015.         res = validate_raise_stmt(tree);
  2016.         break;
  2017.       case import_stmt:
  2018.         res = validate_import_stmt(tree);
  2019.         break;
  2020.       case global_stmt:
  2021.         res = validate_global_stmt(tree);
  2022.         break;
  2023.       case access_stmt:
  2024.         res = validate_access_stmt(tree);
  2025.         break;
  2026.       case exec_stmt:
  2027.         res = validate_exec_stmt(tree);
  2028.         break;
  2029.       case if_stmt:
  2030.         res = validate_if(tree);
  2031.         break;
  2032.       case while_stmt:
  2033.         res = validate_while(tree);
  2034.         break;
  2035.       case for_stmt:
  2036.         res = validate_for(tree);
  2037.         break;
  2038.       case try_stmt:
  2039.         res = validate_try(tree);
  2040.         break;
  2041.       case suite:
  2042.         res = validate_suite(tree);
  2043.         break;
  2044.         /*
  2045.          *  Expression nodes.
  2046.          */
  2047.       case testlist:
  2048.         res = validate_testlist(tree);
  2049.         break;
  2050.       case test:
  2051.         res = validate_test(tree);
  2052.         break;
  2053.       case and_test:
  2054.         res = validate_and_test(tree);
  2055.         break;
  2056.       case not_test:
  2057.         res = validate_not_test(tree);
  2058.         break;
  2059.       case comparison:
  2060.         res = validate_comparison(tree);
  2061.         break;
  2062.       case exprlist:
  2063.         res = validate_exprlist(tree);
  2064.         break;
  2065.       case expr:
  2066.         res = validate_expr(tree);
  2067.         break;
  2068.       case xor_expr:
  2069.         res = validate_xor_expr(tree);
  2070.         break;
  2071.       case and_expr:
  2072.         res = validate_and_expr(tree);
  2073.         break;
  2074.       case shift_expr:
  2075.         res = validate_shift_expr(tree);
  2076.         break;
  2077.       case arith_expr:
  2078.         res = validate_arith_expr(tree);
  2079.         break;
  2080.       case term:
  2081.         res = validate_term(tree);
  2082.         break;
  2083.       case factor:
  2084.         res = validate_factor(tree);
  2085.         break;
  2086.       case atom:
  2087.         res = validate_atom(tree);
  2088.         break;
  2089.         
  2090.       default:
  2091.         /* Hopefully never reached! */
  2092.         res = 0;
  2093.         break;
  2094.     }
  2095.     tree = next;
  2096.     }
  2097.     return (res);
  2098.  
  2099. }   /* validate_node() */
  2100.  
  2101.  
  2102. VALIDATE(expr_tree) {
  2103.     return (validate_ntype(tree, eval_input)
  2104.         && validate_eval_input(tree));
  2105.  
  2106. }   /* validate_expr_tree() */
  2107.  
  2108.  
  2109. VALIDATE(suite_tree) {
  2110.     int j;
  2111.     int nch = NCH(tree);
  2112.     int res = ((nch >= 1)
  2113.            && validate_ntype(CHILD(tree, nch - 1), ENDMARKER)
  2114.            && nch--);
  2115.  
  2116.     for (j = 0; res && (j < nch); ++j) {
  2117.     res = ((TYPE(CHILD(tree, j)) == NEWLINE)
  2118.            || (validate_ntype(CHILD(tree, j), stmt)
  2119.            && validate_stmt(CHILD(tree, j))));
  2120.     }
  2121.     return (res);
  2122.  
  2123. }   /* validate_suite_tree() */
  2124.  
  2125.  
  2126.  
  2127. /*  Functions exported by this module.  Most of this should probably
  2128.  *  be converted into an AST object with methods, but that is better
  2129.  *  done directly in Python, allowing subclasses to be created directly.
  2130.  *  We'd really have to write a wrapper around it all anyway.
  2131.  *
  2132.  */
  2133. static PyMethodDef parser_functions[] =  {
  2134.     {"ast2tuple",    parser_ast2tuple,    1},
  2135.     {"compileast",    parser_compileast,    1},
  2136.     {"expr",        parser_expr,        1},
  2137.     {"isexpr",        parser_isexpr,        1},
  2138.     {"issuite",        parser_issuite,        1},
  2139.     {"suite",        parser_suite,        1},
  2140.     {"tuple2ast",    parser_tuple2ast,    1},
  2141.  
  2142.     {0, 0, 0}
  2143.     };
  2144.  
  2145.  
  2146.  
  2147. void
  2148. initparser() {
  2149.     PyObject* module = Py_InitModule("parser", parser_functions);
  2150.     PyObject* dict   = PyModule_GetDict(module);
  2151.  
  2152.     parser_error = PyString_FromString("parser.ParserError");
  2153.  
  2154.     if ((parser_error == 0)
  2155.     || (PyDict_SetItemString(dict, "ParserError", parser_error) != 0)) {
  2156.     /*
  2157.      *  This is serious.
  2158.      */
  2159.     Py_FatalError("can't define parser.error");
  2160.     }
  2161.     /*
  2162.      *  Nice to have, but don't cry if we fail.
  2163.      */
  2164.     PyDict_SetItemString(dict, "__copyright__",
  2165.              PyString_FromString(parser_copyright_string));
  2166.     PyDict_SetItemString(dict, "__doc__",
  2167.              PyString_FromString(parser_doc_string));
  2168.     PyDict_SetItemString(dict, "__version__",
  2169.              PyString_FromString(parser_version_string));
  2170.  
  2171. }   /* initparser() */
  2172.  
  2173.  
  2174. /*
  2175.  *  end of Parser.c
  2176.  */
  2177.